NO.28 实现strStr() 简单
吐槽一下：这道题的难度标识实在是令人纠结，虽然练习题目才是核心，但是题目的难度标识对于我这样的初学者也是不可缺少的参考标识。
题还没读完，脑海里跳出的第一个想法居然是直接用indexOf()。。。还好立刻就否决了这个想法，但是还是在好奇心的驱使下leetcode提交了一次这个”算法”。。。0ms 100%。。。那就等刷完这道题，读一下indexOf()的源码吧！^_^
思路一：双指针暴力法 1. 用i和j分别指向haystack字符串和needle字符串的开头。2. 如果haystack的i号字符等于needle的j号字符，则j和i都向后移动。3. 如果haystack的i号字符不等于needle的j号字符，则j回到needle字符串的开头，i也回溯之后继续比较。4. 循环直至haystack遍历完毕或者needle遍历完毕。5. 最后如果j指针没有遍历我能needle则说明haystack串不包含needle串，返回-1；反之则返回i-j。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int strStr(String haystack, String needle) {
if (haystack==null||needle==null)throw new NullPointerException();
int i=0,j=0;
for (;i<haystack.length()&&j<needle.length();i++){
if (haystack.charAt(i)==needle.charAt(j)){
j++;
}else {
i=i-j;
j=0;
}
}
return j<needle.length()?-1:i-j;
}
|
时间复杂度：O(m*n)
思路二：Sunday法 该算法的思路相较于KMP十分容易理解，1. 构建一张偏移表，该表主要记录了模式串中的每一个字符，以及每个字符在模式串中出现的最右位置到尾部的距离+1，未在模式串中出现的字符对应的偏移距离都是”模式串长度+1”。2. 有了偏移表之后开始比较，用idx作为当前查询索引，每次截取目标字符串的[idx，idx+模式串长度]子串和模式串比较，如果相等则返回idx。3. 如果不相等，查看子串在目标串中的后一个字符c是否存在于偏移表中，如果存在则idx=idx+偏移表[c]；如果不存在idx=idx+模式串长度+1。循环直至idx+模式串长度>目标字符串长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public int strStr(String haystack,String needle){
if (needle.equals(""))return 0;
int hLen=haystack.length(),nLen=needle.length();
if (hLen<nLen)return -1;
Map<Character,Integer> offsetMap=new HashMap<>();
for (int i=0;i<nLen;i++){
offsetMap.put(needle.charAt(i),nLen-i);
}
int idx=0;
while (idx+nLen<=hLen){
String cutHay = haystack.substring(idx, idx + nLen);
if (cutHay.equals(needle)){
return idx;
}else {
if(idx+nLen>=hLen)return -1;
if (offsetMap.containsKey(haystack.charAt(idx+nLen))){
idx+=offsetMap.get(haystack.charAt(idx+nLen));
}else {
idx+=nLen+1;
}
}
}
return -1;
}
|
时间复杂度：O(m*n)， 但是该算法的平均情况也可以达到O(n)。
思路三：KMP法 数据结构课的时候没学透彻，趁这次机会好好学习一下。作为一只弱鸡，就不瞎扯KMP了，直接找个”巨人肩膀”窥探一下KMP的原理。经过多方查找，最终通过阮一峰的一篇文章艰难入门KMP算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| public int strStr(String haystack, String needle) {
int tarsize = needle.length();
int scrsize = haystack.length();
if(tarsize == 0)
return 0;
if(tarsize > scrsize)
return -1;
if(tarsize == scrsize && needle.equals(haystack))
return 0;
int start = 0;
int i = 0;
int[] next = getNext(needle);
while (start <= scrsize - tarsize)
{
if(haystack.charAt(start + i) == needle.charAt(i))
{
i++;
if(i == tarsize)
return start;
}
else
{
start = start + i - next[i];
i = i > 0 ? next[i] : 0;
}
}
return -1;
}
public int[] getNext(String needle)
{
int tarsize = needle.length();
int[] next = new int[tarsize];
next[0] = -1;
if(tarsize > 1)
next[1] = 0;
int i = 2;
int j = 0;
while(i < tarsize)
{
if(needle.charAt(i-1) == needle.charAt(j))
{
next[i] = j+1;
j++;
i++;
}
else if(j > 0)
{
j = next[j];
}
else
{
next[i] = 0;
i++;
}
}
return next;
}
|
时间复杂度：O(m+n)
本人菜鸟，有错误请告知，感激不尽！
更多题解和学习记录博客:博客、github